package MyMath;

import java.util.Arrays;

/**
 * 1850. 邻位交换的最小次数
 *
 * 给你一个表示大整数的字符串 num ，和一个整数 k 。
 *
 * 如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。
 *
 *     例如，num = "5489355142" ：
 *         第 1 个最小妙数是 "5489355214"
 *         第 2 个最小妙数是 "5489355241"
 *         第 3 个最小妙数是 "5489355412"
 *         第 4 个最小妙数是 "5489355421"
 *
 * 返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。
 *
 * 测试用例是按存在第 k 个最小妙数而生成的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：num = "5489355142", k = 4
 * 输出：2
 * 解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
 * - 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
 * - 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"
 */

public class Leetcode1805 {
    public static int getMinSwaps(String num, int k) {
        int[] nums = new int[num.length()];
        int[] before = new int[num.length()];
        for(int i=0; i<num.length(); i++){
            nums[i] = num.charAt(i)- '0';
            before[i] = num.charAt(i)- '0';
        }

        // 求下第n个数
        while (k>0){
            nextPermutation(nums);
            k--;
        }
        System.out.println(Arrays.toString(nums));

        int len = num.length();
        int res = 0;
        for(int i=0; i<len; i++){
            if(nums[i] != before[i]){
                int j = i+1;
                for (; j<len; j++){
                    if(nums[j] == before[i]){
                        res += (j-i);
                        break;
                    }
                }
                for(int s_idx=j-1; s_idx>=i; s_idx--){
                    swap(nums,s_idx,s_idx+1);
                }
            }
        }

        //求最小交换次数
        return res;
    }

    public static void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return ;
        }
        int len = nums.length;
        int i_index = len - 2;
        // 获取从右往左第一个逆序的，必须要大于
        while (i_index >=0 && nums[i_index] >= nums[i_index + 1]){
            i_index --;
        }

        // 获取从右往左第一个大于i_index的位置，必须要大于
        if(i_index >=0){
            int j_index = len -1;
            while (nums[j_index] <= nums[i_index]){
                j_index --;
            }
            swap(nums, i_index, j_index);
        }
        reverse(nums, i_index+1);
    }

    public static void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 交换i_index-1及其之后的

    public static void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right){
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

    public static void main(String[] args) {
//        String num = "5489355142";
//        int k = 4;
        String num = "11112";
        int k = 4;
        System.out.println(getMinSwaps(num, k));
    }
}
